Tri par comparaison

Cet article présente des problèmes à corriger.

Vous pouvez aider à l'améliorer ou bien discuter des problèmes sur sa page de discussion.

• Il ne cite pas suffisamment ses sources. Vous pouvez indiquer les passages à sourcer avec {{référence nécessaire}} ou {{Référence souhaitée}}, et inclure les références utiles en les liant aux notes de bas de page. (Marqué depuis mars 2024)
• Il doit être débarrassé d’une partie de son jargon. Sa qualité peut être largement améliorée en utilisant un vocabulaire directement compréhensible par le plus grand nombre. (Marqué depuis mars 2024)
• Il contient une ou plusieurs listes. Le texte gagnerait à être rédigé sous la forme d’un ou plusieurs paragraphes synthétiques, afin d’être plus agréable à lire. (Marqué depuis mars 2024)
• Son texte doit être wikifié : il ne correspond pas à la mise en forme Wikipédia (style, typographie, liens internes, liens entre les wikis, etc.). (Marqué depuis novembre 2023)
• Il doit être recyclé. La réorganisation et la clarification du contenu sont nécessaires. (Marqué depuis mars 2024)
• La notion qu'il invoque est trop technique ou pas assez détaillée. Il est préférable de la préciser au moyen d’un lien interne ou d’une note . (Marqué depuis mars 2024)

Trouver des sources sur « Tri par comparaison » :

• Archive Wikiwix
• Bing
• Cairn
• DuckDuckGo
• E. Universalis
• Gallica
• Google
• G. Books
• G. News
• G. Scholar
• Persée
• Qwant
• (zh) Baidu
• (ru) Yandex
• (wd) trouver des œuvres sur Wikidata

Un tri par comparaison est un type d'algorithme de tri qui lit uniquement les éléments de la liste via une seule opération de comparaison abstraite (souvent un opérateur "inférieur ou égal à" ou une comparaison trilatérale) qui détermine lequel des deux éléments doit apparaître en premier dans le liste triée finale. La seule exigence est que l'opérateur soit une relation de préordre total, avec:

1. si a ≤ b et b ≤ c alors a ≤ c (transitivité)
2. pour tout a et b, a ≤ b ou b ≤ a (connexité).

Il est possible que a ≤ b et b ≤ a; dans ce cas, l'un ou l'autre peut apparaître en premier dans la liste triée. Dans un tri stable, l’ordonnancement initial détermine l'ordre des éléments triés.

Une métaphore pour réfléchir aux types de comparaison est que quelqu'un possède un ensemble de poids non étiquetés et une balance. Leur objectif est d'aligner les poids en fonction de leur poids sans aucune information sauf celle obtenue en plaçant deux poids sur la balance et en voyant lequel est le plus lourd (ou s'ils pèsent le même poids).